package 笔试记录.M8day27美团;

import java.util.ArrayList;
import java.util.Scanner;
/*
小团最近获得了美美团团国的裁缝资格证，成为了一个裁缝！现在小团有一个长度为n的大布料S（在这个国家布料其实是一个仅包含小写英文字母的字符串），
小团可以将布料在任意位置剪切，例如布料abcd可以被裁剪为a与bcd 或ab与cd或abc与d ，不过，裁剪完之后是不能拼接起来的，因为小团还不是很擅长拼接布料。
现在小团想知道能不能有一种裁剪方式能让他把布料恰好裁剪成客人要求的小布料。

形式化地，有一个串S，问是否能将其划分成m个不相交的连续子串，使得这些连续子串可以与要求的连续子串一 一对应。两个串相对应是指这两个串完全相等。
例如"aab"="aab" 但 "aab"≠"baa"


 */
public class Main1 {

    static int count = 0;
    static String path = "";

    public static void main(String[] args) {
        //Scanner sc = new Scanner(System.in);
        String s = "aaaaaa";
        ArrayList<String> list = new ArrayList<>();
        list.add("aaaa");
        list.add("aa");
        boolean[] arr = new boolean[list.size()];
        backStacking(list,s,arr,0);
        System.out.println(count);
    }

    public static void backStacking(ArrayList<String> list,String res,boolean[] arr,int index){
        if(path != null && path.length() == res.length()){
            if(path.equals(res)){
                count++;
                return;
            }
        }
        for(int i = index;i < list.size();i++){
            if(i > 0 && list.get(i).equals(list.get(i - 1)) && arr[i - 1] == false){
                continue;
            }
            path += list.get(i);
            arr[i] = true;
            backStacking(list,res,arr,i+1);
            arr[i] = false;
            path = path.substring(0,i + 1);
        }
    }
}
